/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2025-01-13
 * @Description: 
 *******************************************************************************/
#include <iostream>
#include <queue>
#include <sstream>

using namespace std;

class Pet {
public:
    virtual string getType() = 0;
    virtual int getId() = 0;
    virtual int getCount() = 0;
};

class Dog : public Pet {
private:
    string type;
    int id;
    int count;
public:
    Dog(string type, int id, int count) : type(type), id(id), count(count) {}
    string getType() override { return type; }
    int getId() override { return id; }
    int getCount() override { return count; }
};

class Cat : public Pet {
private:
    string type;
    int id;
    int count;
public:
    Cat(string type, int id, int count) : type(type), id(id), count(count) {}
    string getType() override { return type; }
    int getId() override { return id; }
    int getCount() override { return count; }
};

class CatDogQueue {
private:
    queue<Dog* > dogQueue;
    queue<Cat* > catQueue;
public:
    void addPet(Pet *pet) {
        if ("dog" == pet->getType()) {
            dogQueue.push(dynamic_cast<Dog*>(pet));
        } else {
            catQueue.push(dynamic_cast<Cat*>(pet));
        }
    }

    Pet* pollDog() {
        Dog* dog = dogQueue.front();
        dogQueue.pop();
        return dog;
    }

    Cat* pollCat() {
        Cat* cat = catQueue.front();
        catQueue.pop();
        return cat;
    }

    Pet* pollAll() {
        if (!dogQueue.empty() && !catQueue.empty()) {
            if (dogQueue.front()->getCount() < catQueue.front()->getCount()) {
                return pollDog();
            } else {
                return pollCat();
            }
        } else if (!dogQueue.empty()) {
            return pollDog();
        } else {
            return pollCat();
        }
    }

    bool isEmpty() {
        return dogQueue.empty() && catQueue.empty();
    }

    bool isDogEmpty() {
        return dogQueue.empty();
    }

    bool isCatEmpty() {
        return catQueue.empty();
    }
};

int main() {
    int n;
    cin >> n;
    cin.ignore();
    string output;
    int count = 0;
    CatDogQueue queue;
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        istringstream lineStream(line);
        string opt;
        lineStream >> opt;
        if (opt == "add") {
            string type;
            int id;
            lineStream >> type >> id;
            if (type == "dog") {
                queue.addPet(new Dog(type, id, ++count));
            } else {
                queue.addPet(new Cat(type, id, ++count));
            }
        } else if (opt == "pollAll") {
            while (!queue.isEmpty()) {
                Pet* pet = queue.pollAll();
                if (pet->getType() == "dog") {
                    output += "dog " + to_string(pet->getId()) + "\n";
                } else {
                    output += "cat " + to_string(pet->getId()) + "\n";
                }
                delete pet;
            }
        } else if (opt == "pollDog") {
            while (!queue.isDogEmpty()) {
                Pet* dog = queue.pollDog();
                output += "dog " + to_string(dog->getId()) + "\n";
                delete dog;
            }
        } else if (opt == "pollCat") {
            while (!queue.isCatEmpty()) {
                Pet* cat = queue.pollCat();
                output += "cat " + to_string(cat->getId()) + "\n";
                delete cat;
            }
        } else if (opt == "isEmpty") {
            output += (queue.isEmpty() ? "yes\n" : "no\n");
        } else if (opt == "isDogEmpty") {
            output += (queue.isDogEmpty() ? "yes\n" : "no\n");
        } else if (opt == "isCatEmpty") {
            output += (queue.isCatEmpty() ? "yes\n" : "no\n");
        }
    }

    cout << output;
    return 0;
}

